#include "../include/rbtree.h"
#include <stdio.h>

inline rbtree_cmp_result_t rbtree_cmp_def(rbtree_key_t key1, rbtree_key_t key2) {
        if (key1 < key2) {
                return SMALL;
        }
        else if (key1 > key2) {
                return BIG;
        }
        else {
                return EQUAL;
        }
}

inline static _is_leaf(rbtree_t * unit) {
	return unit == NIL;
}

inline static rbtree_t * _father(rbtree_t * unit) {
	return unit->father;
}

inline static rbtree_t * _grandpa(rbtree_t * unit) {
	return unit->father->father;
}

inline static rbtree_t * _uncle(rbtree_t * unit) {
	rbtree_t * p = _grandpa(unit);
	if (p->left == _father(unit)) {
		return p->right;
	}	
	return p->left;
}

inline static rbtree_t * _same(rbtree_t * unit) {
	rbtree_t * p = _father(unit);
	if (p->left == unit) {
		return p->right;
	}
	return p->left;
}

inline static rbtree_head_t * _head(rbtree_t * unit) {
	return unit->head;
}

inline static rbtree_t * _same_left(rbtree_t * unit) {
	return _same(unit)->left;
}

inline static rbtree_t * _same_right(rbtree_t * unit) {
	return _same(unit)->right;
}

inline static void _rotate_right(rbtree_t * unit) {
	rbtree_t * p, *f;
	p = unit->left;
	f = unit->father;
	if (p == NULL)
		return ;

	if (f == NULL) { /* 说明unit是root */
		unit->head->root = p;
	}	
	else {
		if ( f->left == unit ) {
			f->left = p;
		}
		else {
			f->right = p;
		}
	}
	p->father = f;	
	unit->left = p->right;
	if (p->right != NIL) {
		p->right->father = unit;
	}	
	p->right = unit;
	unit->father = p;	
}

inline static void _rotate_left(rbtree_t * unit) {
	rbtree_t * p, *f;
	p = unit->right;
	f = unit->father;
	if (p == NULL) 
		return ;

	if (f == NULL) { /* 说明unit是root */
		unit->head->root = p;					
	}	
	else {
		if ( f->left == unit ) {
			f->left = p;
		}
		else {
			f->right = p;
		}
	}
	p->father = f;
	unit->right = p->left;	
	if (p->left != NIL) {
		p->left->father = unit;
	}
	p->left = unit;
	unit->father = p;
}

inline bool rbtree_is_empty(const rbtree_head_t * head) {
	if (head->root == NIL) {
		return true;
	}
	return false;
}

inline void rbtree_empty(rbtree_head_t * head) {
	head->root = NIL;
	head->op = RBTREE_OP_NULL;
}

inline bool rbtree_is_root(const rbtree_t * unit) {
	return unit->father == NULL;
}

inline cmp_op rbtree_set_cmp(rbtree_head_t * head,const cmp_op op) {
	cmp_op old;
	old = head->op;
	head->op = op;
	return old;	
}

inline void rbtree_set_key(rbtree_t * unit, rbtree_key_t key) {
	unit->key = key;
}

inline rbtree_key_t rbtree_get_key(const rbtree_t * unit) {
	return unit->key;
}

inline rbtree_t * rbtree_find(rbtree_head_t * head, rbtree_key_t key) {
	rbtree_t * p;
	rbtree_cmp_result_t result;

	p = head->root;	
	while (p != NIL) {
		result = head->op(p->key, key);
		if (result == SMALL) {
			p = p->right;
		}
		else if (result == BIG) {
			p = p->left;
		}	
		else {
			return p;
		}			
	}	
	return NULL;
}


/****************************
循环不变式：
	每次开始进入循环时
	1) unit 的color为红色
	2) 红黑树性质1）2) 3）5）成立
	
unit 每次循环后只会指向树中更上层的节点,这是保证循环会终止的条件
需要强调的是，调用_rbtree_insert_adjust时unit一定不是root节点，所以father(unit)一定存在
****************************/
inline void _rbtree_insert_adjust(rbtree_t * unit) {
	rbtree_t * p;
	rbtree_t * g;
	while ( RED == _father(unit)->color ) { /*循环不变式 1）2）都满足*/
		if (NIL != _uncle(unit) && RED == _uncle(unit)->color) {
			_father(unit)->color = BLACK;   /*根据不变式1) unit为红色，这时father为黑色，所以性质4）满足了,但是循环不变式2）被破坏了，因为性质5）不满足了*/	
			_uncle(unit)->color = BLACK;
			_grandpa(unit)->color = RED; /*到这里，循环不变式1）2）又都满足了,因为性质5）又满足了。但是性质4）可能被破坏了,因为_grandpa(unit)变成了红色，而_grandpa(unit)->father可能也是红色*/
			unit = _grandpa(unit);  /*将unit 上浮 */
			if (rbtree_is_root(unit)) {
				unit->color = BLACK; 
				break;   /*性质1）2）3）4）5）都满足了 退出循环*/
			}				
		}	
		else { /*根据循环不变式 unit为red，同时_father(unit)->color 也为红色，说明一定存在grandpa(unit),而且grandpa(unit)->color一定为黑色。在这之前是一个rbtree,所以_father(unit)与_grandpa(unit)应该满足rbtree属性不能同时为红，同时_father(unit)不能为root因为root不能为红色*/

			p = _father(unit);
			g = _grandpa(unit);
			if (g->left == p && p->left == unit) {
				g->color = RED;
				p->color = BLACK;	
				_rotate_right(g);
			}
			else if (g->right == p && p->right == unit){
				g->color = RED;
				p->color = BLACK;
				_rotate_left(g);	
			}		
			else if (g->left == p && p->right == unit) {
				_rotate_left(p); /* p 与 unit 换了个位置 */
				g->color = RED;
				unit->color = BLACK;
				_rotate_right(g);
			}
			else {
				_rotate_right(p); /* p 与 unit 换了个位置 */
				g->color = RED;
				unit->color = BLACK;
				_rotate_left(g);	
			}
			break; /*性质1）2）3）4）5)都满足了*/	
		}
	}
}

inline static rbtree_t * _tree_next(rbtree_t * unit) {
	rbtree_t * p = unit->right;
	rbtree_t * q = p;
	while (p != NIL) {
		q = p;
		p = p->left;
	}
	return q;
}

inline static rbtree_t * _tree_prev(rbtree_t * unit) {
	rbtree_t * p = unit->left;
	rbtree_t * q = p;
	while (p != NIL) {
		q = p;
		p = p->right;
	}
	return q;	
}

inline void rbtree_insert(rbtree_head_t * head, rbtree_t * unit) {
	rbtree_t * p = head->root;
	rbtree_t * q;		
	rbtree_cmp_result_t result;

	if (rbtree_is_empty(head)) {
		head->root = unit;
		unit->father = NULL;
		unit->left = NIL;
		unit->right = NIL;
		unit->color = BLACK;
		unit->head = head;
		return ;
	}

	if (head == _head(unit)) { /* unit 已经在 head 中 */
		return ; 
	}

	while (p != NIL) {
		q = p;
		result = head->op(p->key, unit->key);
		if (BIG == result) {
			p = p->left;
		}
		else if (SMALL == result) {
			p = p->right;	
		}
		else {
			return;  /* 不允许key相同的unit节点存入同一棵rbtree*/
		}
	}
	result = head->op(q->key, unit->key);
	if (BIG == result) {
		q->left = unit;
	}	
	else {
		q->right = unit;
	}
	unit->father = q;
	unit->left = NIL;
	unit->right = NIL;
	unit->color = RED; 
	unit->head = head;
	_rbtree_insert_adjust(unit);
}

inline static void _replace(rbtree_t * x, rbtree_t *y) {
	if (rbtree_is_root(x)) {
		x->head->root = y;
	}
	else {
		if (_father(x)->left == x) {
			x->father->left = y;
		}
		else {
			x->father->right = y;
		}
	}
	if (y != NIL) {
		y->father = x->father;
	}
}
inline static void _swap_color(rbtree_t * x, rbtree_t * y) {
        rbtree_color_t color;
        color = x->color;
        x->color = y->color;
        y->color = color;
}

inline static void _rbtree_delete_adjust(rbtree_t * unit, rbtree_t * p) {
	rbtree_t * s;
	while (unit == NIL || (!rbtree_is_root(unit) && unit->color == BLACK)) {
		if (p->left == unit) {
			s = p->right;
			if (s->color == RED) {
				p->color = RED;
				s->color = BLACK;
				_rotate_left(p);	
				s = p->right;
			}		
			if ((s->left == NIL || s->left->color == BLACK) && (s->right == NIL || s->right->color == BLACK)) {
				s->color = RED;
				unit = p;
				p = p->father;	
				continue;
			}
			else if (s->right == NIL || s->right->color == BLACK){
				s->left->color = BLACK;
				s->color = RED;
				_rotate_right(s);
				s = p->right;	
			}
			s->color = p->color;
			p->color = BLACK;
			s->right->color = BLACK;
			_rotate_left(p);
			unit = s->head->root; 
		}
		else {
			s = p->left;
			if (s->color == RED) {
				p->color = RED;
				s->color = BLACK;
				_rotate_right(p);	
				s = p->left;
			}		
			if ((s->left == NIL || s->left->color == BLACK) && (s->right == NIL || s->right->color == BLACK)) {
				s->color = RED;
				unit = p;
				p = p->father;	
				continue;
			}
			else if (s->left == NIL || s->left->color == BLACK){
				s->right->color = BLACK;
				s->color = RED;
				_rotate_left(s);
				s = p->left;	
			}		
			s->color = p->color;
			p->color = BLACK;
			s->left->color = BLACK;
			_rotate_right(p);
			unit = s->head->root; 
		}			
	}
	unit->color = BLACK;
}

inline void rbtree_delete(rbtree_t * unit) {
	rbtree_head_t * head = unit->head;
	rbtree_t * p;
	rbtree_t * y;
	rbtree_t * x;
	if (unit->left == NIL) {
		x = unit->right;
		p = unit->father;
		_replace(unit, unit->right);
	}
	else if (unit->right == NIL) {
		x = unit->left;
		p = unit->father;
		_replace(unit, unit->left);
	}
	else {
		y = _tree_next(unit);
		x = y->right;
		p = y;
		if (y->father != unit) {
			p = y->father;
			_replace(y, x);	
			y->right = unit->right;
			y->right->father = y;
		}
		_replace(unit, y);	
		_swap_color(unit, y);
		y->left = unit->left;
		y->left->father = y;
	}
	if ( rbtree_is_empty(head) ) {
		return ;
	}		
			
	if ( unit->color == BLACK) {
		_rbtree_delete_adjust(x, p);	
	}

}
